package com.benben.springSecurity.weiwei;

//将等价字符并入一个集合，通过一个数组来维护，两个字符比较，将值存为最小值
//1、初始化一个char 数组，用来存储26个字母；
//2、遍历A，B的的字符，如果相同位置在第1步的数组中不相等，则把1步中的对应字符值修改为字典序小的那个
//3、将S字符串中的字符替换成char数组中的值。
public class SmallestEquivalentString {
    int[] alphabet = new int[26];
    public  String smallestEquivalentString(String A, String B, String S) {
        for(int i=0;i<26;i++){
            alphabet[i] = i;
        }
        for(int i=0;i<A.length();i++){
            union(A.charAt(i)-'a',B.charAt(i)-'a');
        }
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<S.length();i++){
            char c = S.charAt(i);
            sb.append(findSmall(c-'a')+'a');
        }
        return sb.toString();
    }

    private  int findSmall(int i){
        while(alphabet[i]!=i){
            i = alphabet[i];
        }
        return i;
    }

    private  void union(int a,int b){
        int aa = findSmall(a);
        int bb = findSmall(b);
        int small = Math.min(aa,bb);
        alphabet[aa] = small;
        alphabet[bb] = small;
    }

}
